package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/18 22:07
 * @description:  力扣322 零钱兑换
 */
public class CoinChange {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int amount = sr.nextInt();
        sr.nextLine();

        String []str = sr.nextLine().split(" ");
        int [] coins = new int[str.length];
        for(int i = 0;i < str.length;i++){
            coins[i] = Integer.valueOf(str[i]);
        }
        int ans = new ConinChange_Solution().coinChange(coins,amount);
        System.out.println(ans);
    }
}
class ConinChange_Solution{

    public int coinChange(int[] coins, int amount) {

        int []dp = new int[amount+1]; //dp[i] 表示金额之和等于i的硬币组合数，
        dp[0] = 1;  //只有当不选取任何硬币时，金额之和才为0，因此只有1种硬币组合

        //对于面额为coin的硬币，当coin <= i <= amount时，如果存在一种硬币组合金额之和等于i-coin ,则在该硬币
        //组合中增加一个面额为coin的硬币，即可得到一种金额之和等于i的硬币的组合，因此需要遍历coins，对于其中的每一种面额的硬币，
        //更新dp数组中的每个大于或等于该面额的元素的值。
        for(int coin :coins){
            for(int i = coin; i<=amount;i++){
                dp[i] += dp[i - coin];      //dp[i]可能会随着coin的遍历，累加很多次
            }
        }
        return dp[amount];
    }
}